<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.21.2: https://docutils.sourceforge.io/" />
<title>The BM25 Weighting Scheme</title>
<style type="text/css">

/*
:Author: David Goodger (goodger@python.org)
:Id: $Id: html4css1.css 9511 2024-01-13 09:50:07Z milde $
:Copyright: This stylesheet has been placed in the public domain.

Default cascading style sheet for the HTML output of Docutils.
Despite the name, some widely supported CSS2 features are used.

See https://docutils.sourceforge.io/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/

/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
  border: 0 }

table.borderless td, table.borderless th {
  /* Override padding for "table.docutils td" with "! important".
     The right padding separates the table cells. */
  padding: 0 0.5em 0 0 ! important }

.first {
  /* Override more specific margin styles with "! important". */
  margin-top: 0 ! important }

.last, .with-subtitle {
  margin-bottom: 0 ! important }

.hidden {
  display: none }

.subscript {
  vertical-align: sub;
  font-size: smaller }

.superscript {
  vertical-align: super;
  font-size: smaller }

a.toc-backref {
  text-decoration: none ;
  color: black }

blockquote.epigraph {
  margin: 2em 5em ; }

dl.docutils dd {
  margin-bottom: 0.5em }

object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
  overflow: hidden;
}

/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
  font-weight: bold }
*/

div.abstract {
  margin: 2em 5em }

div.abstract p.topic-title {
  font-weight: bold ;
  text-align: center }

div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
  margin: 2em ;
  border: medium outset ;
  padding: 1em }

div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
  font-weight: bold ;
  font-family: sans-serif }

div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title, .code .error {
  color: red ;
  font-weight: bold ;
  font-family: sans-serif }

/* Uncomment (and remove this text!) to get reduced vertical space in
   compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
  margin-bottom: 0.5em }

div.compound .compound-last, div.compound .compound-middle {
  margin-top: 0.5em }
*/

div.dedication {
  margin: 2em 5em ;
  text-align: center ;
  font-style: italic }

div.dedication p.topic-title {
  font-weight: bold ;
  font-style: normal }

div.figure {
  margin-left: 2em ;
  margin-right: 2em }

div.footer, div.header {
  clear: both;
  font-size: smaller }

div.line-block {
  display: block ;
  margin-top: 1em ;
  margin-bottom: 1em }

div.line-block div.line-block {
  margin-top: 0 ;
  margin-bottom: 0 ;
  margin-left: 1.5em }

div.sidebar {
  margin: 0 0 0.5em 1em ;
  border: medium outset ;
  padding: 1em ;
  background-color: #ffffee ;
  width: 40% ;
  float: right ;
  clear: right }

div.sidebar p.rubric {
  font-family: sans-serif ;
  font-size: medium }

div.system-messages {
  margin: 5em }

div.system-messages h1 {
  color: red }

div.system-message {
  border: medium outset ;
  padding: 1em }

div.system-message p.system-message-title {
  color: red ;
  font-weight: bold }

div.topic {
  margin: 2em }

h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
  margin-top: 0.4em }

h1.title {
  text-align: center }

h2.subtitle {
  text-align: center }

hr.docutils {
  width: 75% }

img.align-left, .figure.align-left, object.align-left, table.align-left {
  clear: left ;
  float: left ;
  margin-right: 1em }

img.align-right, .figure.align-right, object.align-right, table.align-right {
  clear: right ;
  float: right ;
  margin-left: 1em }

img.align-center, .figure.align-center, object.align-center {
  display: block;
  margin-left: auto;
  margin-right: auto;
}

table.align-center {
  margin-left: auto;
  margin-right: auto;
}

.align-left {
  text-align: left }

.align-center {
  clear: both ;
  text-align: center }

.align-right {
  text-align: right }

/* reset inner alignment in figures */
div.align-right {
  text-align: inherit }

/* div.align-center * { */
/*   text-align: left } */

.align-top    {
  vertical-align: top }

.align-middle {
  vertical-align: middle }

.align-bottom {
  vertical-align: bottom }

ol.simple, ul.simple {
  margin-bottom: 1em }

ol.arabic {
  list-style: decimal }

ol.loweralpha {
  list-style: lower-alpha }

ol.upperalpha {
  list-style: upper-alpha }

ol.lowerroman {
  list-style: lower-roman }

ol.upperroman {
  list-style: upper-roman }

p.attribution {
  text-align: right ;
  margin-left: 50% }

p.caption {
  font-style: italic }

p.credits {
  font-style: italic ;
  font-size: smaller }

p.label {
  white-space: nowrap }

p.rubric {
  font-weight: bold ;
  font-size: larger ;
  color: maroon ;
  text-align: center }

p.sidebar-title {
  font-family: sans-serif ;
  font-weight: bold ;
  font-size: larger }

p.sidebar-subtitle {
  font-family: sans-serif ;
  font-weight: bold }

p.topic-title {
  font-weight: bold }

pre.address {
  margin-bottom: 0 ;
  margin-top: 0 ;
  font: inherit }

pre.literal-block, pre.doctest-block, pre.math, pre.code {
  margin-left: 2em ;
  margin-right: 2em }

pre.code .ln { color: gray; } /* line numbers */
pre.code, code { background-color: #eeeeee }
pre.code .comment, code .comment { color: #5C6576 }
pre.code .keyword, code .keyword { color: #3B0D06; font-weight: bold }
pre.code .literal.string, code .literal.string { color: #0C5404 }
pre.code .name.builtin, code .name.builtin { color: #352B84 }
pre.code .deleted, code .deleted { background-color: #DEB0A1}
pre.code .inserted, code .inserted { background-color: #A3D289}

span.classifier {
  font-family: sans-serif ;
  font-style: oblique }

span.classifier-delimiter {
  font-family: sans-serif ;
  font-weight: bold }

span.interpreted {
  font-family: sans-serif }

span.option {
  white-space: nowrap }

span.pre {
  white-space: pre }

span.problematic, pre.problematic {
  color: red }

span.section-subtitle {
  /* font-size relative to parent (h1..h6 element) */
  font-size: 80% }

table.citation {
  border-left: solid 1px gray;
  margin-left: 1px }

table.docinfo {
  margin: 2em 4em }

table.docutils {
  margin-top: 0.5em ;
  margin-bottom: 0.5em }

table.footnote {
  border-left: solid 1px black;
  margin-left: 1px }

table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
  padding-left: 0.5em ;
  padding-right: 0.5em ;
  vertical-align: top }

table.docutils th.field-name, table.docinfo th.docinfo-name {
  font-weight: bold ;
  text-align: left ;
  white-space: nowrap ;
  padding-left: 0 }

/* "booktabs" style (no vertical lines) */
table.docutils.booktabs {
  border: 0px;
  border-top: 2px solid;
  border-bottom: 2px solid;
  border-collapse: collapse;
}
table.docutils.booktabs * {
  border: 0px;
}
table.docutils.booktabs th {
  border-bottom: thin solid;
  text-align: left;
}

h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
  font-size: 100% }

ul.auto-toc {
  list-style-type: none }

</style>
</head>
<body>
<div class="document" id="the-bm25-weighting-scheme">
<h1 class="title">The BM25 Weighting Scheme</h1>

<p>This is a technical note about the BM25 weighting scheme, which is the
default weighting scheme used by Xapian. Recent TREC tests have shown
BM25 to be the best of the known probabilistic weighting schemes. In
case you're wondering, the BM simply stands for &quot;Best Match&quot;.</p>
<p>We'll follow the evolution from the &quot;traditional&quot; probabilistic
weighting scheme (as described in the <a class="reference external" href="http://www.soi.city.ac.uk/~ser/papers/RSJ76.pdf">1976 Robertson/Sparck Jones
paper</a>) through to
BM25.</p>
<div class="section" id="the-traditional-probabilistic-weighting-scheme">
<h1>The Traditional Probabilistic Weighting Scheme</h1>
<p>In its most general form, the traditional probabilistic term weighting
function is:</p>
<div class="formula">
<span class="fraction"><span class="ignored">(</span><span class="numerator">(<i>k</i><sub>3</sub> + 1)<i>q</i></span><span class="ignored">)/(</span><span class="denominator">(<i>k</i><sub>3</sub> + <i>q</i>)</span><span class="ignored">)</span></span><span class="text"> * </span><span class="fraction"><span class="ignored">(</span><span class="numerator">(<i>k</i><sub>1</sub> + 1)<i>f</i></span><span class="ignored">)/(</span><span class="denominator">(<i>k</i><sub>1</sub><i>L</i> + <i>f</i>)</span><span class="ignored">)</span></span><span class="text"> * </span>log<span class="fraction"><span class="ignored">(</span><span class="numerator">(<i>r</i> + 0.5)(<i>N</i> − <i>n</i> − <i>R</i> + <i>r</i> + 0.5)</span><span class="ignored">)/(</span><span class="denominator">(<i>n</i> − <i>r</i> + 0.5)(<i>R</i> − <i>r</i> + 0.5)</span><span class="ignored">)</span></span>...(1)
</div>
<p>where</p>
<blockquote>
<ul class="simple">
<li><span class="formula"><i>k</i><sub>1</sub></span>, <span class="formula"><i>k</i><sub>3</sub></span> are constants,</li>
<li>q is the wqf, the within query frequency,</li>
<li>f is the wdf, the within document frequency,</li>
<li>n is the number of documents in the collection indexed by this term,</li>
<li>N is the total number of documents in the collection,</li>
<li>r is the number of relevant documents indexed by this term,</li>
<li>R is the total number of relevant documents,</li>
<li>L is the normalised document length (i.e. the length of this document
divided by the average length of documents in the collection).</li>
</ul>
</blockquote>
<p>The factors <span class="formula">(<i>k</i><sub>3</sub> + 1)</span> and <span class="formula">(<i>k</i><sub>1</sub> + 1)</span> are unnecessary here, but help
scale the weights, so the first component is 1 when <span class="formula"><i>q</i> = 1</span> etc. But
they are critical below when we add an extra item to the sum of term
weights.</p>
</div>
<div class="section" id="bm11">
<h1>BM11</h1>
<p>Stephen Robertson's BM11 uses formula <span class="formula">(1)</span> for the term weights, but
adds an extra item to the sum of term weights to give the overall
document score:</p>
<div class="formula">
<i>k</i><sub>2</sub><i>n</i><sub><i>q</i></sub><span class="fraction"><span class="ignored">(</span><span class="numerator">(1 − <i>L</i>)</span><span class="ignored">)/(</span><span class="denominator">(1 + <i>L</i>)</span><span class="ignored">)</span></span>...(2)
</div>
<p>where:</p>
<ul class="simple">
<li><span class="formula"><i>n</i><sub><i>q</i></sub></span> is the number of terms in the query (the query length),</li>
<li><span class="formula"><i>k</i><sub>2</sub></span> is yet another constant.</li>
</ul>
<p>Note that this extra item is zero when <span class="formula"><i>L</i> = 1</span>.</p>
</div>
<div class="section" id="bm15">
<h1>BM15</h1>
<p>BM15 is BM11 with the <span class="formula"><i>k</i><sub>1</sub> + <i>f</i></span> in place of <span class="formula"><i>k</i><sub>1</sub><i>L</i> + <i>f</i></span> in <span class="formula">(1)</span>.</p>
</div>
<div class="section" id="bm25">
<h1>BM25</h1>
<p>BM25 combines the B11 and B15 with a scaling factor, b, which turns BM15
into BM11 as it moves from 0 to 1:</p>
<div class="formula">
<span class="fraction"><span class="ignored">(</span><span class="numerator">(<i>k</i><sub>3</sub> + 1)<i>q</i></span><span class="ignored">)/(</span><span class="denominator">(<i>k</i><sub>3</sub> + <i>q</i>)</span><span class="ignored">)</span></span><span class="text"> * </span><span class="fraction"><span class="ignored">(</span><span class="numerator">(<i>k</i><sub>1</sub> + 1)<i>f</i></span><span class="ignored">)/(</span><span class="denominator">(<i>K</i> + <i>f</i>)</span><span class="ignored">)</span></span><span class="text"> * </span>log<span class="fraction"><span class="ignored">(</span><span class="numerator">(<i>r</i> + 0.5)(<i>N</i> − <i>n</i> − <i>R</i> + <i>r</i> + 0.5)</span><span class="ignored">)/(</span><span class="denominator">(<i>n</i> − <i>r</i> + 0.5)(<i>R</i> − <i>r</i> + 0.5)</span><span class="ignored">)</span></span>...(3)
</div>
<p>where:</p>
<p><span class="formula"><i>K</i> = <i>k</i><sub>1</sub>(<i>bL</i> + (1 − <i>b</i>))</span></p>
<p>BM25 originally introduced another constant, as a power to which f and K
are raised. However, Stephen remarks that powers other than 1 were <em>'not
helpful'</em>, and other tests confirm this, so Xapian's implementation of
BM25 ignores this.</p>
<p><span class="formula">(2)</span> and <span class="formula">(3)</span> make up BM25, with which Stephen has had so much
recent success.</p>
<p>This does all seem somewhat ad-hoc, with so many unknown constants in
the formula. But note that with <span class="formula"><i>k</i><sub>2</sub> = 0</span> and <span class="formula"><i>b</i> = 1</span> we get the
traditional formula anyway.</p>
<p>The default parameter values Xapian uses are <span class="formula"><i>k</i><sub>1</sub> = 1</span>, <span class="formula"><i>k</i><sub>2</sub> = 0</span>,
<span class="formula"><i>k</i><sub>3</sub> = 1</span>,and <span class="formula"><i>b</i> = 0.5</span>. These are reasonable defaults, but the
optimum values will vary with both the documents being searched and the
type of queries, so you may be able to improve the effectiveness of your
search system by tuning the values of these parameters.</p>
<p>In Xapian, we also apply a floor to L (0.5 by default) which helps stop
tiny documents get ridiculously high weights. And the matcher wants the
extra item in the sum to be positive, so we add <span class="formula"><i>k</i><sub>2</sub><i>n</i><sub><i>q</i></sub></span> (constant for a
given query) to <span class="formula">(2)</span> to give:</p>
<div class="formula">
<span class="fraction"><span class="ignored">(</span><span class="numerator">2<i>k</i><sub>2</sub><i>n</i><sub><i>q</i></sub></span><span class="ignored">)/(</span><span class="denominator">(1 + <i>L</i>)</span><span class="ignored">)</span></span>...(4)
</div>
</div>
</div>
</body>
</html>
